package xiaomin.demo.algorithm;

public class Lesson12 {
    public static void run(){
        int[] arr={11,3,6,4,7,3,5,8,9,3,4,6,8,9,10,22,33,56,1,44,767,34,356,432};
        int k=7;
        int index=-1;
        int start=0,end=arr.length-1;
        while ((index-1)!=k){
            index=getIndex(arr,start,end);
            if(k<(index-1)){
                end=index-1;
            }
            if((index-1)<k){
                start=index+1;
            }
        }

        for(int x:arr) {
            System.out.println(x);
        }

    }

    public static int getIndex(int[] arr,int start,int end){
        //第一个数字
        int tmp=arr[start];
        //双向区间扫描
        while (start<end){
            //先从end扫描
            while (start<end && arr[end]>=tmp){
                end--;
            }
            //遇到小的,填坑到左边
            arr[start]=arr[end];
            //从start扫描
            while(start<end && arr[start]<=tmp){
                start++;
            }
            //遇到大的,填坑到右边
            arr[end]=arr[start];
        }

        arr[start]=tmp;

        return start;
    }
}
